{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Amount of Time for Binary Tree to Be Infected"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: amountOfTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #感染二叉树需要的总时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树的根节点 <code>root</code> ，二叉树中节点的值 <strong>互不相同</strong> 。另给你一个整数 <code>start</code> 。在第 <code>0</code> 分钟，<strong>感染</strong> 将会从值为 <code>start</code> 的节点开始爆发。</p>\n",
    "\n",
    "<p>每分钟，如果节点满足以下全部条件，就会被感染：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点此前还没有感染。</li>\n",
    "\t<li>节点与一个已感染节点相邻。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回感染整棵树需要的分钟数<em>。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/06/25/image-20220625231744-1.png\" style=\"width: 400px; height: 306px;\">\n",
    "<pre><strong>输入：</strong>root = [1,5,3,null,4,10,6,9,2], start = 3\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>节点按以下过程被感染：\n",
    "- 第 0 分钟：节点 3\n",
    "- 第 1 分钟：节点 1、10、6\n",
    "- 第 2 分钟：节点5\n",
    "- 第 3 分钟：节点 4\n",
    "- 第 4 分钟：节点 9 和 2\n",
    "感染整棵树需要 4 分钟，所以返回 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/06/25/image-20220625231812-2.png\" style=\"width: 75px; height: 66px;\">\n",
    "<pre><strong>输入：</strong>root = [1], start = 1\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>第 0 分钟，树中唯一一个节点处于感染状态，返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在范围 <code>[1, 10<sup>5</sup>]</code> 内</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li>每个节点的值 <strong>互不相同</strong></li>\n",
    "\t<li>树中必定存在值为 <code>start</code> 的节点</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [amount-of-time-for-binary-tree-to-be-infected](https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [amount-of-time-for-binary-tree-to-be-infected](https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,5,3,null,4,10,6,9,2]\\n3', '[1]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parent = dict()\n",
    "        stack = deque([root])\n",
    "        while stack:\n",
    "            cur = stack.popleft()\n",
    "            if cur.val == start:\n",
    "                break\n",
    "            if cur.left:\n",
    "                stack.append(cur.left)\n",
    "                parent[cur.left] = cur\n",
    "            if cur.right:\n",
    "                stack.append(cur.right)\n",
    "                parent[cur.right] = cur\n",
    "            \n",
    "        level = -1\n",
    "        stack = [cur]\n",
    "        visited = set()\n",
    "        while stack:\n",
    "            temp = []\n",
    "            for cur in stack:\n",
    "                if cur in parent and parent[cur].val not in visited:   temp.append(parent[cur])\n",
    "                if cur.left and cur.left.val not in visited:    temp.append(cur.left)\n",
    "                if cur.right and cur.right.val not in visited:   temp.append(cur.right)\n",
    "                visited.add(cur.val)\n",
    "            level += 1\n",
    "            stack = temp\n",
    "        return level"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parent = dict()\n",
    "        stack = deque([root])\n",
    "        while stack:\n",
    "            cur = stack.popleft()\n",
    "            if cur.val == start:\n",
    "                break\n",
    "            if cur.left:\n",
    "                stack.append(cur.left)\n",
    "                parent[cur.left] = cur\n",
    "            if cur.right:\n",
    "                stack.append(cur.right)\n",
    "                parent[cur.right] = cur\n",
    "            \n",
    "        level = -1\n",
    "        stack = [cur]\n",
    "        visited = set()\n",
    "        while stack:\n",
    "            temp = []\n",
    "            for cur in stack:\n",
    "                if cur in parent and parent[cur].val not in visited:   temp.append(parent[cur])\n",
    "                if cur.left and cur.left.val not in visited:    temp.append(cur.left)\n",
    "                if cur.right and cur.right.val not in visited:   temp.append(cur.right)\n",
    "                visited.add(cur.val)\n",
    "            level += 1\n",
    "            stack = temp\n",
    "        return level"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parent = dict()\n",
    "        stack = deque([root])\n",
    "        while stack:\n",
    "            cur = stack.popleft()\n",
    "            if cur.val == start:\n",
    "                break\n",
    "            if cur.left:\n",
    "                stack.append(cur.left)\n",
    "                parent[cur.left] = cur\n",
    "            if cur.right:\n",
    "                stack.append(cur.right)\n",
    "                parent[cur.right] = cur\n",
    "            \n",
    "        level = -1\n",
    "        stack = [cur]\n",
    "        visited = set()\n",
    "        while stack:\n",
    "            temp = []\n",
    "            for cur in stack:\n",
    "                if cur in parent and parent[cur].val not in visited:   temp.append(parent[cur])\n",
    "                if cur.left and cur.left.val not in visited:    temp.append(cur.left)\n",
    "                if cur.right and cur.right.val not in visited:   temp.append(cur.right)\n",
    "                visited.add(cur.val)\n",
    "            level += 1\n",
    "            stack = temp\n",
    "        return level"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parent = dict()\n",
    "        stack = deque([root])\n",
    "        while stack:\n",
    "            cur = stack.popleft()\n",
    "            if cur.val == start:\n",
    "                break\n",
    "            if cur.left:\n",
    "                stack.append(cur.left)\n",
    "                parent[cur.left] = cur\n",
    "            if cur.right:\n",
    "                stack.append(cur.right)\n",
    "                parent[cur.right] = cur\n",
    "            \n",
    "        level = -1\n",
    "        stack = [cur]\n",
    "        visited = set()\n",
    "        while stack:\n",
    "            temp = []\n",
    "            for cur in stack:\n",
    "                if cur in parent and parent[cur].val not in visited:   temp.append(parent[cur])\n",
    "                if cur.left and cur.left.val not in visited:    temp.append(cur.left)\n",
    "                if cur.right and cur.right.val not in visited:   temp.append(cur.right)\n",
    "                visited.add(cur.val)\n",
    "            level += 1\n",
    "            stack = temp\n",
    "        return level"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        e=collections.defaultdict(list)\n",
    "        q=collections.deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            tp=q.pop()\n",
    "            if not tp:\n",
    "                continue\n",
    "            if tp.left:\n",
    "                e[tp.val].append(tp.left.val)\n",
    "                e[tp.left.val].append(tp.val)\n",
    "                q.append(tp.left)\n",
    "            if tp.right:\n",
    "                e[tp.val].append(tp.right.val)\n",
    "                e[tp.right.val].append(tp.val)\n",
    "                q.append(tp.right)\n",
    "        print(e)\n",
    "        find=set()\n",
    "        q.append((start,0))\n",
    "        ans=0\n",
    "        while q:\n",
    "            tp,d=q.popleft()\n",
    "            print(tp,d)\n",
    "            if tp in find:\n",
    "                continue\n",
    "            find.add(tp)\n",
    "            ans=max(ans,d)\n",
    "            for i in e[tp]:\n",
    "                if i not in find:\n",
    "                    q.append((i,d+1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        # graph to store every node's parent-child info\n",
    "        g = defaultdict(list)\n",
    "        status = defaultdict(bool)\n",
    "        q = deque([root])\n",
    "\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            status[node.val] = False \n",
    "            if node.left:\n",
    "                g[node.left.val].append(node.val)\n",
    "                g[node.val].append(node.left.val)\n",
    "                q.append(node.left)\n",
    "            if node.right:\n",
    "                g[node.right.val].append(node.val)\n",
    "                g[node.val].append(node.right.val)\n",
    "                q.append(node.right)  \n",
    "        # start node True\n",
    "        status[start] = True  \n",
    "\n",
    "        # BFS check\n",
    "        ans = 0\n",
    "        q = deque([start])\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                for each in g[node]:\n",
    "                    if status[each] == False:\n",
    "                        status[each] = True\n",
    "                        q.append(each)\n",
    "            ans += 1\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        g = defaultdict(list)  # 图\n",
    "        status = defaultdict(bool)  # 节点状态 False未感染 True感染\n",
    "        # BFS建图\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            status[node.val] = False\n",
    "            if node.left:\n",
    "                g[node.val].append(node.left.val)\n",
    "                g[node.left.val].append(node.val)\n",
    "                q.append(node.left)\n",
    "            if node.right:\n",
    "                g[node.val].append(node.right.val)\n",
    "                g[node.right.val].append(node.val)\n",
    "                q.append(node.right)\n",
    "        \n",
    "        status[start] = True\n",
    "        \n",
    "        # BFS\n",
    "        ans = 0\n",
    "        q = deque([start])\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                for each in g[node]:  # 感染相邻节点\n",
    "                    if status[each] == False:\n",
    "                        status[each] = True\n",
    "                        q.append(each)\n",
    "            ans += 1\n",
    "        \n",
    "        return ans - 1\n",
    "    \n",
    "        # # find start and every node's parent\n",
    "        # parents = {}\n",
    "        # def dfs(node, parent):\n",
    "        #     if node is None:\n",
    "        #         return\n",
    "        #     if node.val == start:\n",
    "        #         self.start = node\n",
    "        #     parents[node] = parent\n",
    "        #     dfs(node.left, node)\n",
    "        #     dfs(node.right, node)\n",
    "        # dfs(root, None)\n",
    "\n",
    "        # ans = -1\n",
    "        # visit = {None, self.start}\n",
    "        # q = [self.start]\n",
    "        # while q:\n",
    "        #     ans += 1\n",
    "        #     temp = q\n",
    "        #     q = []\n",
    "        #     for node in temp:\n",
    "        #         for x in node.left, node.right, parents[node]:\n",
    "        #             if x not in visit:\n",
    "        #                 visit.add(x)\n",
    "        #                 q.append(x)\n",
    "        # return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        g = defaultdict(list)  # 图\n",
    "        status = defaultdict(bool)  # 节点状态 False未感染 True感染\n",
    "        # BFS建图\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            status[node.val] = False\n",
    "            if node.left:\n",
    "                g[node.val].append(node.left.val)\n",
    "                g[node.left.val].append(node.val)\n",
    "                q.append(node.left)\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "                g[node.val].append(node.right.val)\n",
    "                g[node.right.val].append(node.val)\n",
    "        \n",
    "        status[start] = True\n",
    "        \n",
    "        # BFS\n",
    "        ans = -1\n",
    "        q = deque([start])\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                for each in g[node]:  # 感染相邻节点\n",
    "                    if status[each] == False:\n",
    "                        status[each] = True\n",
    "                        q.append(each)\n",
    "            ans += 1\n",
    "        \n",
    "        return ans\n",
    "    \n",
    "        # # find start and every node's parent\n",
    "        # parents = {}\n",
    "        # def dfs(node, parent):\n",
    "        #     if node is None:\n",
    "        #         return\n",
    "        #     if node.val == start:\n",
    "        #         self.start = node\n",
    "        #     parents[node] = parent\n",
    "        #     dfs(node.left, node)\n",
    "        #     dfs(node.right, node)\n",
    "        # dfs(root, None)\n",
    "\n",
    "        # ans = -1\n",
    "        # visit = {None, self.start}\n",
    "        # q = [self.start]\n",
    "        # while q:\n",
    "        #     ans += 1\n",
    "        #     temp = q\n",
    "        #     q = []\n",
    "        #     for node in temp:\n",
    "        #         for x in node.left, node.right, parents[node]:\n",
    "        #             if x not in visit:\n",
    "        #                 visit.add(x)\n",
    "        #                 q.append(x)\n",
    "        # return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        status = defaultdict(bool)\n",
    "        # BFS建图\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            status[node.val] = False\n",
    "            if node.left:\n",
    "                g[node.val].append(node.left.val)\n",
    "                g[node.left.val].append(node.val)\n",
    "                q.append(node.left)\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "                g[node.val].append(node.right.val)\n",
    "                g[node.right.val].append(node.val)\n",
    "\n",
    "        status[start] = True\n",
    "\n",
    "        # BFS\n",
    "        ans = 0\n",
    "        q = deque([start])\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                for each in g[node]:  # 感染相邻节点\n",
    "                    if not status[each]:\n",
    "                        status[each] = True\n",
    "                        q.append(each)\n",
    "            ans += 1\n",
    "\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        # find g  {3: 1, 10 ,6} {10:3} {6:3}\n",
    "        g = defaultdict(list) \n",
    "        status = defaultdict(bool)\n",
    "        q = deque([root]) \n",
    "\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            status[node] = False # uninfected\n",
    "            if node.left:\n",
    "                g[node.left.val].append(node.val)\n",
    "                g[node.val].append(node.left.val)\n",
    "                q.append(node.left) \n",
    "            if node.right:\n",
    "                g[node.right.val].append(node.val)\n",
    "                g[node.val].append(node.right.val)\n",
    "                q.append(node.right) \n",
    "        \n",
    "        # status [] False: uninfected True: infect\n",
    "        status[start] = True # infected\n",
    "        ans = 0\n",
    "        q = deque([start])\n",
    "        # BFS to check starting start to graph \n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                for each in g[node]: # infect neighbor\n",
    "                    if status[each] == False:\n",
    "                        status[each] = True\n",
    "                        q.append(each)\n",
    "            ans += 1\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "\n",
    "        res = -inf\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            if node:\n",
    "                L,LFlag = dfs(node.left)\n",
    "                R,RFlag = dfs(node.right)\n",
    "\n",
    "                if node.val == start:\n",
    "                    res = max(res,L,R)\n",
    "                    return 1,True\n",
    "\n",
    "                if LFlag or RFlag:\n",
    "                    res = max(res,L+R)\n",
    "                    if LFlag:\n",
    "                        return L+1,True\n",
    "                    if RFlag:\n",
    "                        return R+1,True\n",
    "                else:\n",
    "                    return max(L,R) + 1,False\n",
    "            else:\n",
    "                return 0,False\n",
    "        dfs(root)\n",
    "        return res\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return -1, False\n",
    "            l, lflag = dfs(node.left)\n",
    "            r, rflag = dfs(node.right)\n",
    "            if node.val == start:\n",
    "                ans = max(l, r) + 1\n",
    "                return 0, True\n",
    "            if lflag or rflag:\n",
    "                ans = max(ans, l+r+2)\n",
    "                curr = l+1 if lflag else r+1\n",
    "                return curr, True\n",
    "            return max(l, r)+1, False\n",
    "            \n",
    "        ans = 0\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        ans=0\n",
    "        def f(node):\n",
    "            nonlocal ans\n",
    "            x1,y1,x2,y2=0,False,0,False\n",
    "            if node.left:\n",
    "                x1,y1=f(node.left)\n",
    "                x1+=1\n",
    "            if node.right:\n",
    "                x2,y2=f(node.right)\n",
    "                x2+=1\n",
    "            if y1 or y2:\n",
    "                ans=max(ans,x1+x2)\n",
    "            if y1:\n",
    "                return (x1,True)\n",
    "            if y2:\n",
    "                return (x2,True)\n",
    "            if node.val==start:\n",
    "                ans=max(ans,x1,x2)\n",
    "                return (0,True)\n",
    "            return (max(x1,x2),False)\n",
    "        f(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        ans=0\n",
    "        def f(node: Optional[TreeNode])->tuple:\n",
    "            nonlocal ans\n",
    "            x1,y1,x2,y2=0,False,0,False\n",
    "            if node.left:#如果有左节点\n",
    "                x1,y1=f(node.left)\n",
    "                x1 +=1\n",
    "            if node.right:\n",
    "                x2,y2=f(node.right)\n",
    "                x2 +=1\n",
    "            if y1 or y2:\n",
    "                ans=max(ans,x1+x2)\n",
    "            if y1:\n",
    "                return (x1,y1)\n",
    "            if y2:\n",
    "                return (x2,y2)\n",
    "            if node.val==start:\n",
    "                ans=max(ans,x1,x2)\n",
    "                return (0,True)\n",
    "            return (max(x1,x2),False)\n",
    "        f(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        self.level = - 1\n",
    "        res = 0\n",
    "        def dfs(node, level):\n",
    "            nonlocal res \n",
    "            if not node:\n",
    "                return 0\n",
    "            if node.val == start:\n",
    "                self.level = level\n",
    "            l = dfs(node.left, level + 1)\n",
    "            inLeft = (self.level != - 1)\n",
    "            r = dfs(node.right, level + 1)\n",
    "            if node.val == start:\n",
    "                res = max(res, l, r)\n",
    "            elif inLeft:\n",
    "                res = max(res, self.level - level + r)\n",
    "            else:\n",
    "                res = max(res, self.level - level + l)\n",
    "            return max(l, r) + 1\n",
    "        dfs(root, 0)\n",
    "        return res \n",
    "\n",
    "\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        self.level = - 1\n",
    "        res = 0\n",
    "        def dfs(node, level):\n",
    "            if not node:\n",
    "                return 0\n",
    "            nonlocal res\n",
    "            if node.val == start:\n",
    "                self.level = level\n",
    "            l = dfs(node.left, level + 1)\n",
    "            inLeft = (self.level != - 1)\n",
    "            r = dfs(node.right, level + 1)\n",
    "            if node.val == start:\n",
    "                res = max(res, l, r)\n",
    "            elif inLeft:\n",
    "                res = max(res, self.level - level + r)\n",
    "            else:\n",
    "                res = max(res, self.level - level + l)\n",
    "            return max(l, r) + 1\n",
    "\n",
    "        dfs(root, 0)\n",
    "        return res \n",
    "\n",
    "\n",
    "        def dfs(node, level):\n",
    "            if not node:\n",
    "                return 0\n",
    "            nonlocal res\n",
    "            if node.val == start:\n",
    "                self.level = level\n",
    "            l = dfs(node.left, level + 1)\n",
    "            inLeft = (self.level != - 1)\n",
    "            r = dfs(node.right, level + 1)\n",
    "            if node.val == start:\n",
    "                res = max(res, l, r)\n",
    "            elif inLeft:\n",
    "                res = max(res, self.level - level + r)\n",
    "            else:\n",
    "                res = max(res, self.level - level + l)\n",
    "            return max(l, r) + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        self.level = - 1\n",
    "        res = 0\n",
    "        def dfs(node, level):\n",
    "            if not node:\n",
    "                return 0\n",
    "            nonlocal res\n",
    "            if node.val == start:\n",
    "                self.level = level\n",
    "            l = dfs(node.left, level + 1)\n",
    "            inLeft = (self.level != - 1)\n",
    "            r = dfs(node.right, level + 1)\n",
    "            if node.val == start:\n",
    "                res = max(res, l, r)\n",
    "            elif inLeft:\n",
    "                res = max(res, self.level - level + r)\n",
    "            else:\n",
    "                res = max(res, self.level - level + l)\n",
    "            return max(l, r) + 1\n",
    "        dfs(root, 0)\n",
    "        return res \n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    startDepth = -1\n",
    "    result = 0\n",
    "\n",
    "    def dfs(self, root: Optional[TreeNode], level: int, start: int) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        if root.val == start:\n",
    "            self.startDepth = level\n",
    "        l = self.dfs(root.left, level + 1, start)\n",
    "        inLeft = self.startDepth != -1\n",
    "        r = self.dfs(root.right, level + 1, start)\n",
    "        if root.val == start:\n",
    "            self.result = max(l, r)\n",
    "        elif inLeft:\n",
    "            self.result = max(self.result, self.startDepth - level + r)\n",
    "        else:\n",
    "            self.result = max(self.result, self.startDepth - level + l)\n",
    "        return 1 + max(l, r)\n",
    "    \n",
    "    \n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        self.dfs(root, 0, start)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        self.level = - 1\n",
    "        res = 0\n",
    "        def dfs(node, level):\n",
    "            nonlocal res \n",
    "            if not node:\n",
    "                return 0\n",
    "            if node.val == start:\n",
    "                self.level = level\n",
    "            l = dfs(node.left, level + 1)\n",
    "            inLeft = (self.level != - 1)\n",
    "            r = dfs(node.right, level + 1)\n",
    "            if node.val == start:\n",
    "                res = max(res, l, r)\n",
    "            elif inLeft:\n",
    "                res = max(res, self.level - level + r)\n",
    "            else:\n",
    "                res = max(res, self.level - level + l)\n",
    "            return max(l, r) + 1\n",
    "        dfs(root, 0)\n",
    "        return res \n",
    "\n",
    "\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        self.level = - 1\n",
    "        res = 0\n",
    "        def dfs(node, level):\n",
    "            nonlocal res \n",
    "            if not node:\n",
    "                return 0\n",
    "            if node.val == start:\n",
    "                self.level = level\n",
    "            l = dfs(node.left, level + 1)\n",
    "            inLeft = self.level != - 1\n",
    "            r = dfs(node.right, level + 1)\n",
    "            if node.val == start:\n",
    "                res = max(res, l, r)\n",
    "            elif inLeft:\n",
    "                res = max(res, self.level - level + r)\n",
    "            else:\n",
    "                res = max(res, self.level - level + l)\n",
    "            return max(l, r) + 1\n",
    "        dfs(root, 0)\n",
    "        return res \n",
    "\n",
    "\n",
    "        self.level = - 1\n",
    "        res = 0\n",
    "        def dfs(node, level):\n",
    "            nonlocal res \n",
    "            if not node:\n",
    "                return 0\n",
    "            if node.val == start:\n",
    "                self.level = level\n",
    "            l = dfs(node.left, level + 1)\n",
    "            inLeft = self.level != - 1\n",
    "            r = dfs(node.right, level + 1)\n",
    "            if node.val == start:\n",
    "                res = max(res, l + r)\n",
    "            elif inLeft:\n",
    "                res = max(res, self.level - level + r)\n",
    "            else:\n",
    "                res = max(res, self.level - level + l)\n",
    "            return max(l, r) + 1\n",
    "        dfs(root, 0)\n",
    "        return res \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        self.parents = {}\n",
    "        self.start = start\n",
    "        self.startnode = None\n",
    "        self.dfs(root, None)\n",
    "        return self.bfs(self.startnode)\n",
    "    def dfs(self, node, parent):\n",
    "        if node is None:\n",
    "            return\n",
    "        if node.val == self.start:\n",
    "            self.startnode = node\n",
    "        self.parents[node]=parent\n",
    "        self.dfs(node.left, node)\n",
    "        self.dfs(node.right, node)\n",
    "    def bfs(self, node):\n",
    "        queue = [node]\n",
    "        ans = -1\n",
    "        index = 0\n",
    "        vis = {None,node}#none.left not right\n",
    "        notend = True\n",
    "        while notend:\n",
    "            ans+=1\n",
    "            temp = len(queue)\n",
    "            notend = False\n",
    "            for i in range(index, len(queue)):\n",
    "                nodetemp = queue[i]\n",
    "                for x in [nodetemp.left, nodetemp.right, self.parents[nodetemp]]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        queue.append(x)\n",
    "                        notend = True\n",
    "            index = temp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parent = {}\n",
    "        def dfs(root: Optional[TreeNode]):\n",
    "            if root is None: return\n",
    "            if root.val == start:\n",
    "                parent[root] = 1\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            if parent:\n",
    "                parent[root] = len(parent) + 1\n",
    "                return\n",
    "            dfs(root.right)\n",
    "            if parent:\n",
    "                parent[root] = len(parent) + 1\n",
    "                return\n",
    "        dfs(root)\n",
    "\n",
    "        def bfs(root: Optional[TreeNode]) -> int:\n",
    "            r, a = 0, [root]\n",
    "            while a:\n",
    "                b = a\n",
    "                a = []\n",
    "                for t in b:\n",
    "                    if t.left is not None and t.left not in parent:\n",
    "                        a.append(t.left)\n",
    "                    if t.right is not None and t.right not in parent:\n",
    "                        a.append(t.right)\n",
    "                r += 1\n",
    "            return r - 1\n",
    "        ans = 0\n",
    "        for k in parent:\n",
    "            ans = max(ans, bfs(k) + parent[k] - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parents = {}\n",
    "        def dfs(node:Optional[TreeNode], pa:Optional[TreeNode]) -> None:\n",
    "            if node is None: return\n",
    "            if node.val == start: self.start = node\n",
    "            parents[node] = pa\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        vis = {None, self.start}\n",
    "        q = [self.start]\n",
    "        while q:\n",
    "            ans += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        # 先求出每一个节点的父节点\n",
    "        parents = {}\n",
    "        def dfs(node, pa):\n",
    "            if not node: return\n",
    "            if node.val == start: self.start = node\n",
    "\n",
    "            parents[node] = pa\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "    \n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        q = [self.start]\n",
    "        vis = {None, self.start}\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            ans += 1\n",
    "            for node in tmp:\n",
    "                # 当前节点的父节点，子节点都会在1s内被感染\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        # find start and every node's parent\n",
    "        parents = {}\n",
    "        def dfs(node, parent):\n",
    "            if node is None:\n",
    "                return\n",
    "            if node.val == start:\n",
    "                self.start = node\n",
    "            parents[node] = parent\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        visit = {None, self.start}\n",
    "        q = [self.start]\n",
    "        while q:\n",
    "            ans += 1\n",
    "            temp = q\n",
    "            q = []\n",
    "            for node in temp:\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in visit:\n",
    "                        visit.add(x)\n",
    "                        q.append(x)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parents = {}\n",
    "        def dfs(node: Optional[TreeNode], pa: Optional[TreeNode]) -> None:\n",
    "            if node is None: return\n",
    "            if node.val == start: self.start = node\n",
    "            parents[node] = pa\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        vis = {None, self.start}\n",
    "        q = [self.start]\n",
    "        while q:\n",
    "            ans += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        # bfs 模拟：\n",
    "        parents = {}\n",
    "        def dfs(node:Optional[TreeNode], pa:Optional[TreeNode]) -> None:\n",
    "            if node is None: return\n",
    "            if node.val == start: self.start = node\n",
    "            parents[node] = pa\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        vis = {None, self.start}\n",
    "        q = [self.start]\n",
    "        while q:\n",
    "            ans += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        father = {}\n",
    "        def dfs(root, fa):\n",
    "            if not root:\n",
    "                return \n",
    "            if fa != -1: father[root] = fa\n",
    "            if root.val == start:\n",
    "                nonlocal q\n",
    "                q = [root]\n",
    "            dfs(root.left, root)\n",
    "            dfs(root.right, root)\n",
    "        q = []\n",
    "        dfs(root, -1)\n",
    "        ans = 0\n",
    "        vis = set()\n",
    "        vis.add(q[0])\n",
    "        while q:\n",
    "            tmp, q = q, []\n",
    "            for node in tmp:\n",
    "                if node.left and node.left not in vis:\n",
    "                    q.append(node.left)\n",
    "                    vis.add(node.left)\n",
    "                if node.right and node.right not in vis:\n",
    "                    q.append(node.right)\n",
    "                    vis.add(node.right)  \n",
    "                if node in father and father[node] not in vis:\n",
    "                    q.append(father[node])\n",
    "                    vis.add(father[node])  \n",
    "            ans += 1\n",
    "        return ans -1\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        father = {}\n",
    "        def dfs(root, fa):\n",
    "            if not root:\n",
    "                return \n",
    "            father[root] = fa\n",
    "            if root.val == start:\n",
    "                self.start = root\n",
    "            dfs(root.left, root)\n",
    "            dfs(root.right, root)\n",
    "\n",
    "        dfs(root, None)\n",
    "        ans = -1\n",
    "        vis = {None, self.start}\n",
    "        q = [self.start]\n",
    "        while q:\n",
    "            tmp, q = q, []\n",
    "            for node in tmp:\n",
    "                for x in node.left, node.right, father[node]:\n",
    "                    if x not in vis:\n",
    "                        q.append(x)\n",
    "                        vis.add(x)\n",
    "            ans += 1\n",
    "        return ans\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parents = {}\n",
    "        def dfs(node: Optional[TreeNode], pa: Optional[TreeNode]) -> None:\n",
    "            if node is None: return\n",
    "            if node.val == start: self.start = node\n",
    "            parents[node] = pa\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        vis = {None, self.start}\n",
    "        q = [self.start]\n",
    "        while q:\n",
    "            ans += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parents = {}\n",
    "        def dfs(node: Optional[TreeNode], pa: Optional[TreeNode]) -> None:\n",
    "            if node is None: return\n",
    "            if node.val == start: self.start = node\n",
    "            parents[node] = pa\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        vis = {None, self.start}\n",
    "        q = [self.start]\n",
    "        while q:\n",
    "            ans += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parents = {}\n",
    "        def dfs(node: Optional[TreeNode], pa: Optional[TreeNode]) -> None:\n",
    "            if node is None: return\n",
    "            if node.val == start: self.start = node\n",
    "            parents[node] = pa\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        vis = {None, self.start}\n",
    "        q = [self.start]\n",
    "        while q:\n",
    "            ans += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parents = {}\n",
    "        def dfs(node: Optional[TreeNode], pa: Optional[TreeNode]) -> None:\n",
    "            if node is None: return\n",
    "            if node.val == start: self.start = node\n",
    "            parents[node] = pa\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        vis = {None, self.start}\n",
    "        q = [self.start]\n",
    "        while q:\n",
    "            ans += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parents = {}\n",
    "        def dfs(node: Optional[TreeNode], pa: Optional[TreeNode]) -> None:\n",
    "            if node is None: return\n",
    "            if node.val == start: self.start = node\n",
    "            parents[node] = pa\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        vis = {None, self.start}\n",
    "        q = [self.start]\n",
    "        while q:\n",
    "            ans += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parents = {}\n",
    "        def dfs(node, pa):\n",
    "            if not node:\n",
    "                return\n",
    "            parents[node] = pa\n",
    "            if node.val == start:\n",
    "                self.start = node\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        q = [self.start]\n",
    "        vis = {self.start, None}\n",
    "        while q:\n",
    "            ans +=1\n",
    "            temp = q\n",
    "            q = []\n",
    "            for node in temp:\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parents = {}\n",
    "        def dfs(node: Optional[TreeNode], pa: Optional[TreeNode]) -> None:\n",
    "            if node is None: return\n",
    "            if node.val == start: self.start = node\n",
    "            parents[node] = pa\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        vis = {None, self.start}\n",
    "        q = [self.start]\n",
    "        while q:\n",
    "            ans += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parents = {}\n",
    "        def dfs(node: Optional[TreeNode], pa: Optional[TreeNode]) -> None:\n",
    "            if node is None: return\n",
    "            if node.val == start: self.start = node\n",
    "            parents[node] = pa\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        vis = {None, self.start}\n",
    "        q = [self.start]\n",
    "        while q:\n",
    "            ans += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        first = None\n",
    "        parent = {}\n",
    "\n",
    "        def set_parent(node):\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            if node.val == start:\n",
    "                nonlocal first\n",
    "                first = node\n",
    "\n",
    "            if node.left:\n",
    "                parent[node.left] = node\n",
    "                set_parent(node.left)\n",
    "\n",
    "            if node.right:\n",
    "                parent[node.right] = node\n",
    "                set_parent(node.right)\n",
    "\n",
    "        set_parent(root)\n",
    "\n",
    "        queue = deque([first])\n",
    "        visited = set(queue)\n",
    "        minute = -1\n",
    "\n",
    "        while queue:\n",
    "            minute += 1\n",
    "            n = len(queue)\n",
    "\n",
    "            for _ in range(n):\n",
    "                head = queue.popleft()\n",
    "                if head != root and parent[head] not in visited:\n",
    "                    visited.add(parent[head])\n",
    "                    queue.append(parent[head])\n",
    "                if head.left and head.left not in visited:\n",
    "                    visited.add(head.left)\n",
    "                    queue.append(head.left)\n",
    "                if head.right and head.right not in visited:\n",
    "                    visited.add(head.right)\n",
    "                    queue.append(head.right)\n",
    "\n",
    "        return minute\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parents = {}\n",
    "        def dfs(node: Optional[TreeNode], pa: Optional[TreeNode]) -> None:\n",
    "            if node is None: return\n",
    "            if node.val == start: self.start = node\n",
    "            parents[node] = pa\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        vis = {None, self.start}\n",
    "        q = [self.start]\n",
    "        while q:\n",
    "            ans += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        # 有两种方式，一种是dfs先找到start，并建立图，再bfs算时间\n",
    "        # 另一种是一次dfs搞定，sum(left, max(m, n)) 如示例1中，m = 1, n = 1, left = 3\n",
    "        # 先用方式1的笨办法吧\n",
    "        parents = {}\n",
    "        def dfs(node, pa) -> None:\n",
    "            if node is None: return \n",
    "            if node.val == start: self.start = node\n",
    "            parents[node] = pa\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        vis = {None, self.start}\n",
    "        q = [self.start]\n",
    "        while q:\n",
    "            ans += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        \n",
    "        def findParent(node: TreeNode, parent: TreeNode) -> None:\n",
    "            \"\"\"DFS递归遍历当前节点的树\n",
    "                用哈希表记录父节点\n",
    "                找到start值对应的节点startnode\n",
    "                T: O(N)\n",
    "            \"\"\"\n",
    "            nonlocal startNode\n",
    "            if not node:\n",
    "                return \n",
    "            \n",
    "            # 找到start值对应的节点startnode\n",
    "            if node.val == start:\n",
    "                startNode = node \n",
    "            \n",
    "            hashmap[node.val] = parent \n",
    "            findParent(node.left, node)\n",
    "            findParent(node.right, node)\n",
    "\n",
    "        def bfs(node: TreeNode, dist: int) -> None:\n",
    "            \"\"\"\n",
    "            BFS traversal of tree rooted at `node` along 3 directions (left subtree, right subtree, parent node)\n",
    "\n",
    "            dist: distance between `node` and start node\n",
    "            T: O(N)\n",
    "            \"\"\"\n",
    "            nonlocal ans \n",
    "            queue = collections.deque([(node, dist)])\n",
    "            \n",
    "            while queue:\n",
    "                node, dist = queue.popleft()\n",
    "                if not node or node in visited:\n",
    "                    continue\n",
    "                ans = max(ans, dist)\n",
    "                \n",
    "                visited.add(node)\n",
    "                \n",
    "                queue.append((node.left, dist + 1))\n",
    "                queue.append((node.right, dist + 1))\n",
    "                queue.append((hashmap[node.val], dist + 1))\n",
    "\n",
    "        ans = 0                     # 初始化最大距离\n",
    "        startNode = None           # initialize start node\n",
    "        hashmap = dict()           # 哈希表: 从根节点出发，记录所有节点的父节点 \n",
    "        visited = set()            # 集合：记录已访问节点\n",
    "        findParent(root, None)      # 初始化 根节点的父节点为None\n",
    "        bfs(startNode, 0)           # infect from startNode\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        \n",
    "        parent = {}\n",
    "        self.st = None\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            if root.val == start:\n",
    "                self.st = root\n",
    "            \n",
    "            if root.left:\n",
    "                parent[root.left] = root\n",
    "            \n",
    "            if root.right:\n",
    "                parent[root.right] = root\n",
    "\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "\n",
    "        parent[root] = None\n",
    "        dfs(root)\n",
    "\n",
    "        seen = set([self.st])\n",
    "        queue = collections.deque([self.st])\n",
    "        step = -1\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "                if parent[node] and parent[node] not in seen:\n",
    "                    queue.append(parent[node])\n",
    "                    seen.add(parent[node])\n",
    "                \n",
    "                if node.left and node.left not in seen:\n",
    "                    queue.append(node.left)\n",
    "                    seen.add(node.left)\n",
    "                \n",
    "                if node.right and node.right not in seen:\n",
    "                    queue.append(node.right)\n",
    "                    seen.add(node.right)\n",
    "\n",
    "\n",
    "            step += 1\n",
    "\n",
    "        return step\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        # 先求出每一个节点的父节点\n",
    "        parents = {}\n",
    "        def dfs(node, pa):\n",
    "            if not node: return\n",
    "            if node.val == start: self.start = node\n",
    "\n",
    "            parents[node] = pa\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "    \n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        q = [self.start]\n",
    "        vis = {None, self.start}\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            ans += 1\n",
    "            for node in tmp:\n",
    "                # 当前节点的父节点，子节点都会在1s内被感染\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        #i#f root.val==start:\n",
    "          #  return 0\n",
    "        p={}\n",
    "        x=-1\n",
    "        def dfs(r,fa):\n",
    "            nonlocal x\n",
    "            if not r:\n",
    "                return \n",
    "            if r.val==start:\n",
    "                x=r\n",
    "            \n",
    "            p[r]=fa\n",
    "            dfs(r.left,r)\n",
    "            dfs(r.right,r)\n",
    "            return \n",
    "        dfs(root,None)\n",
    "        stack=collections.deque()\n",
    "        #print(p)\n",
    "        stack.append([0,x])\n",
    "        mx=0\n",
    "        vis=set()\n",
    "        vis.add(x)\n",
    "        while stack:\n",
    "            d,cur=stack.popleft()\n",
    "            if d>mx:\n",
    "                mx=d\n",
    "            if cur.left and cur.left not in vis:\n",
    "                stack.append([d+1,cur.left])\n",
    "                vis.add(cur.left)\n",
    "            if cur.right and cur.right not in vis:\n",
    "                stack.append([d+1,cur.right])\n",
    "                vis.add(cur.right)\n",
    "            if p[cur] and p[cur] not in vis:\n",
    "                stack.append([d+1,p[cur]])\n",
    "                vis.add(p[cur])\n",
    "\n",
    "        return mx\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        # 先求出每一个节点的父节点\n",
    "        parents = {}\n",
    "        def dfs(node, pa):\n",
    "            if not node: return\n",
    "            if node.val == start: self.start = node\n",
    "\n",
    "            parents[node] = pa\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "    \n",
    "        dfs(root, None)\n",
    "\n",
    "        ans = -1\n",
    "        q = [self.start]\n",
    "        vis = {None, self.start}\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            ans += 1\n",
    "            for node in tmp:\n",
    "                # 当前节点的父节点，子节点都会在1s内被感染\n",
    "                for x in node.left, node.right, parents[node]:\n",
    "                    if x not in vis:\n",
    "                        vis.add(x)\n",
    "                        q.append(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parent = dict()\n",
    "\n",
    "        def findParent(root):\n",
    "            if not root: return\n",
    "            if root.left:\n",
    "                parent[root.left.val] = root\n",
    "                findParent(root.left)\n",
    "            \n",
    "            if root.right:\n",
    "                parent[root.right.val] = root\n",
    "                findParent(root.right)\n",
    "        \n",
    "        findParent(root)\n",
    "        answer = 0\n",
    "\n",
    "        def findTarget(node):\n",
    "            if not node: return None\n",
    "            return node if node.val == start else (findTarget(node.left) or findTarget(node.right))\n",
    "        \n",
    "        target = findTarget(root)\n",
    "\n",
    "        def helper(root, prev, minutes):\n",
    "            if not root:\n",
    "                return\n",
    "            nonlocal answer\n",
    "            answer = max(answer, minutes)\n",
    "\n",
    "            if root.left    != prev:\n",
    "                helper(root.left,       root, minutes + 1)\n",
    "\n",
    "            if root.right   != prev:\n",
    "                helper(root.right,      root, minutes + 1)\n",
    "\n",
    "            if root.val in parent and parent[root.val] != prev:\n",
    "                helper(parent[root.val],root, minutes + 1)\n",
    "            \n",
    "        helper(target, None, 0)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "    \t\t\t\tn = 10 ** 5 + 1\n",
    "    \t\t\t\tg = [[] for _ in range(n)]\n",
    "    \t\t\t\tdef dfs(root: Optional[TreeNode], p: int) -> None:\n",
    "    \t\t\t\t\t\t\t\tif p != -1:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tg[root.val].append(p)\n",
    "    \t\t\t\t\t\t\t\tif root.left:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tg[root.val].append(root.left.val)\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tdfs(root.left, root.val)\n",
    "    \t\t\t\t\t\t\t\tif root.right:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tg[root.val].append(root.right.val)\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tdfs(root.right, root.val)\n",
    "    \t\t\t\tdfs(root, -1)\n",
    "    \t\t\t\tstep = -1\n",
    "    \t\t\t\tq = deque()\n",
    "    \t\t\t\tq.append(start)\n",
    "    \t\t\t\tvis = set()\n",
    "    \t\t\t\tvis.add(start)\n",
    "    \t\t\t\twhile q:\n",
    "    \t\t\t\t\t\t\t\tsize = len(q)\n",
    "    \t\t\t\t\t\t\t\tfor _ in range(size):\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tp = q.popleft()\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tfor y in g[p]:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tif y not in vis:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tvis.add(y)\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tq.append(y)\n",
    "    \t\t\t\t\t\t\t\tstep += 1\n",
    "    \t\t\t\treturn step\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\t\n",
    "    \t\t\t\t\t\t\t\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        cnt=[[0]*3 for _ in range(100001)]\n",
    "        def dfs1(node: Optional[TreeNode])-> int:\n",
    "            if not node: return 0\n",
    "            cnt[node.val][0]=dfs1(node.left)\n",
    "            cnt[node.val][1]=dfs1(node.right)\n",
    "            return max(cnt[node.val][0],cnt[node.val][1])+1\n",
    "\n",
    "        def dfs2(node: Optional[TreeNode],sum_ : int):\n",
    "            if not node: return\n",
    "            cnt[node.val][2]=sum_\n",
    "            dfs2(node.left,max(cnt[node.val][1],sum_)+1)\n",
    "            dfs2(node.right,max(cnt[node.val][0],sum_)+1)\n",
    "            \n",
    "        dfs1(root)\n",
    "        dfs2(root,0)\n",
    "\n",
    "        return max(cnt[start])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "\n",
    "        target = None\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            if node.val == start:\n",
    "                nonlocal target\n",
    "                target = node\n",
    "            if node.left:\n",
    "                node.left.fa = node\n",
    "                dfs(node.left)\n",
    "            if node.right:\n",
    "                node.right.fa = node\n",
    "                dfs(node.right)\n",
    "        root.fa = None\n",
    "        dfs(root)\n",
    "        q = [target]\n",
    "        s = set([start])\n",
    "        step = 0\n",
    "        while True:\n",
    "            tmp = q\n",
    "            q = []            \n",
    "            for node in tmp:\n",
    "                for son in [node.left, node.right, node.fa]:\n",
    "                    if not son or son.val in s:\n",
    "                        continue\n",
    "                    s.add(son.val)\n",
    "                    q.append(son)\n",
    "            if q == []:\n",
    "                return step\n",
    "            step += 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        dic={}\n",
    "        cdic={}\n",
    "        n=0\n",
    "        def inorder(node):\n",
    "            nonlocal dic,n\n",
    "            if node:\n",
    "                n+=1\n",
    "                inorder(node.left)\n",
    "                cdic[node.val]=0\n",
    "                if node.left:\n",
    "                    if node.val in dic:\n",
    "                        dic.get(node.val).append(node.left.val)\n",
    "                    else:\n",
    "                        dic[node.val]=[node.left.val]\n",
    "                    if node.left.val in dic:\n",
    "                        dic.get(node.left.val).append(node.val)\n",
    "                    else:\n",
    "                        dic[node.left.val]=[node.val]\n",
    "                if node.right:\n",
    "                    if node.val in dic:\n",
    "                        dic.get(node.val).append(node.right.val)\n",
    "                    else:\n",
    "                        dic[node.val]=[node.right.val]\n",
    "                    if node.right.val in dic:\n",
    "                        dic.get(node.right.val).append(node.val)\n",
    "                    else:\n",
    "                        dic[node.right.val]=[node.val]\n",
    "                inorder(node.right)\n",
    "        inorder(root)\n",
    "        queue=[start]\n",
    "        ans=0\n",
    "        while queue:\n",
    "            level=[]\n",
    "            temp=queue[:]\n",
    "            print(temp)\n",
    "            for n in temp:\n",
    "                if cdic[n]!=1:\n",
    "                    cdic[n]=1\n",
    "                    if n in dic:\n",
    "                        for a in dic[n]:\n",
    "                            if cdic[a]!=1:\n",
    "                                level.append(a)\n",
    "            queue=level[:]\n",
    "            ans+=1\n",
    "        return ans-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "\n",
    "        def findParent(node: TreeNode, parent: TreeNode) -> None:\n",
    "            \"\"\"DFS递归遍历当前节点的树，用哈希表记录父节点\n",
    "            \"\"\"\n",
    "            nonlocal startNode\n",
    "            if not node:\n",
    "                return \n",
    "            \n",
    "            # 找到start值对应的节点startnode\n",
    "            if node.val == start:\n",
    "                startNode = node \n",
    "            \n",
    "            hashmap[node.val] = parent \n",
    "            findParent(node.left, node)\n",
    "            findParent(node.right, node)\n",
    "\n",
    "        def dfs(node: TreeNode, dist: int) -> None:\n",
    "            \"\"\"\n",
    "            从当前节点出发，DFS递归地沿3个方向感染（左子树、右子树、父节点）\n",
    "\n",
    "            node: 当前节点\n",
    "            dist: 当前距离\n",
    "            \"\"\"\n",
    "            nonlocal ans\n",
    "            # 递归终止条件：遇到空节点，直接返回\n",
    "            if not node or node in visited:\n",
    "                return\n",
    "\n",
    "            ans = max(ans, dist) # 更新最大深度\n",
    "            visited.add(node)\n",
    "            dfs(node.left, dist+1)  # 感染左子树\n",
    "            dfs(node.right, dist+1) # 感染右子树\n",
    "            dfs(hashmap[node.val], dist+1) # 感染父节点\n",
    "\n",
    "        ans = 0   # 初始化最大距离\n",
    "        startNode = None \n",
    "        hashmap = dict()           # 哈希表: 从根节点出发，记录所有节点的父节点 \n",
    "        visited = set()            # 集合：记录已访问节点\n",
    "        findParent(root, None) # 初始化 根节点的父节点为None\n",
    "        dfs(startNode, 0)  # 从startnode开始感染\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "\n",
    "        def findParent(node: TreeNode, parent: TreeNode) -> None:\n",
    "            \"\"\"DFS递归遍历当前节点的树，用哈希表记录父节点\n",
    "            \"\"\"\n",
    "            nonlocal startNode\n",
    "            if not node:\n",
    "                return \n",
    "            \n",
    "            # 找到start值对应的节点startnode\n",
    "            if node.val == start:\n",
    "                startNode = node \n",
    "            \n",
    "            hashmap[node.val] = parent \n",
    "            findParent(node.left, node)\n",
    "            findParent(node.right, node)\n",
    "\n",
    "        def dfs(node: TreeNode, dist: int) -> None:\n",
    "            \"\"\"\n",
    "            从当前节点出发，DFS递归地沿3个方向感染（左子树、右子树、父节点）\n",
    "\n",
    "            node: 当前节点\n",
    "            dist: 当前距离\n",
    "            \"\"\"\n",
    "            nonlocal ans\n",
    "            # 递归终止条件：遇到空节点，直接返回\n",
    "            if not node or node in visited:\n",
    "                return\n",
    "\n",
    "            ans = max(ans, dist) # 更新最大深度\n",
    "            visited.add(node)\n",
    "            dfs(node.left, dist+1)  # 感染左子树\n",
    "            dfs(node.right, dist+1) # 感染右子树\n",
    "            dfs(hashmap[node.val], dist+1) # 感染父节点\n",
    "\n",
    "        ans = -1   # 初始化最大距离\n",
    "        startNode = None \n",
    "        hashmap = dict()           # 哈希表: 从根节点出发，记录所有节点的父节点 \n",
    "        visited = set()            # 集合：记录已访问节点\n",
    "        findParent(root, None) # 初始化 根节点的父节点为None\n",
    "        dfs(startNode, 0)  # 从startnode开始感染\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        def dfs(pa, tn):\n",
    "            if tn:\n",
    "                if pa != -1:\n",
    "                    g[tn.val].append(pa)\n",
    "                    g[pa].append(tn.val)\n",
    "                dfs(tn.val, tn.left)\n",
    "                dfs(tn.val, tn.right)\n",
    "        dfs(-1, root)\n",
    "        q = [(start, 0)]\n",
    "        dis = [-1] * 100010\n",
    "        dis[start] = 0\n",
    "        ans = 0\n",
    "        while q:\n",
    "            nq = []\n",
    "            for x, t in q:\n",
    "                ans = max(ans, t)\n",
    "                for y in g[x]:\n",
    "                    if dis[y] == -1:\n",
    "                        dis[y] = t + 1\n",
    "                        nq.append((y, t + 1))\n",
    "            q = nq\n",
    "        return ans \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        dic = defaultdict(list)\n",
    "        def dfs(root):\n",
    "            if not root.left and not root.right:\n",
    "                return\n",
    "            if root.left:\n",
    "                dic[root.val].append(root.left.val)\n",
    "                dic[root.left.val].append(root.val)\n",
    "                dfs(root.left)\n",
    "            if root.right:\n",
    "                dic[root.val].append(root.right.val)\n",
    "                dic[root.right.val].append(root.val)\n",
    "                dfs(root.right)\n",
    "            return\n",
    "        dfs(root)\n",
    "        v = set([start])\n",
    "        q = deque([[start,0]])\n",
    "        while q:\n",
    "            temp = q.popleft()\n",
    "            print(temp)\n",
    "            ans = temp[1]\n",
    "            for ne in dic[temp[0]]:\n",
    "                if ne in v:\n",
    "                    continue\n",
    "                v.add(ne)\n",
    "                q.append([ne,temp[1]+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        height = defaultdict(int)\n",
    "        def getHeight(node: Optional[TreeNode]) -> int:\n",
    "            if not node:\n",
    "                return 0\n",
    "            left, right = getHeight(node.left), getHeight(node.right)\n",
    "            height[node.val] = max(left, right) + 1\n",
    "            return height[node.val]\n",
    "        getHeight(root)\n",
    "\n",
    "        def helper(node: Optional[TreeNode], othLength: int) -> int:\n",
    "            if not node:\n",
    "                return -inf\n",
    "            if node.val == start:\n",
    "                return max(othLength, height[node.val] - 1)\n",
    "            left = height[node.left.val] if node.left else 0\n",
    "            right = height[node.right.val] if node.right else 0\n",
    "            return max(helper(node.left, max(othLength, right) + 1), helper(node.right, max(othLength, left) + 1))\n",
    "        return helper(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        \n",
    "        self.graph = collections.defaultdict(list)\n",
    "        self.que = collections.deque()\n",
    "        self.visited = set()\n",
    "        \n",
    "        def makegraph(root, graph):\n",
    "            if not root:return\n",
    "            if root.left:\n",
    "                graph[root.left.val].append(root.val)\n",
    "                graph[root.val].append(root.left.val)\n",
    "                makegraph(root.left, graph)\n",
    "            if root.right:\n",
    "                graph[root.right.val].append(root.val)\n",
    "                graph[root.val].append(root.right.val)\n",
    "                makegraph(root.right, graph)\n",
    "                \n",
    "        makegraph(root, self.graph)\n",
    "        \n",
    "        def bfs(root, start):\n",
    "            res = -1\n",
    "            self.que.append(start)\n",
    "            self.visited.add(start)\n",
    "            \n",
    "            while self.que:\n",
    "                #print(self.que)\n",
    "                size = len(self.que)\n",
    "                res += 1\n",
    "                for _ in range(size):\n",
    "                    node = self.que.popleft()\n",
    "                    for son_node in self.graph[node]:\n",
    "                        if son_node not in self.visited:\n",
    "                            self.que.append(son_node)\n",
    "                            self.visited.add(son_node)\n",
    "            return res\n",
    "        return bfs(root, start)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        graph = {}\n",
    "        def traversal(root,fa):\n",
    "            if(not root):\n",
    "                return\n",
    "            if(root.val not in graph):\n",
    "                graph[root.val] = []\n",
    "            if(fa):\n",
    "                graph[root.val].append(fa.val)\n",
    "            if(root.left):\n",
    "                graph[root.val].append(root.left.val)\n",
    "            if(root.right):\n",
    "                graph[root.val].append(root.right.val)\n",
    "            traversal(root.left,root)\n",
    "            traversal(root.right,root)\n",
    "            return\n",
    "        traversal(root,None)\n",
    "        que = deque()\n",
    "        que.append([start,0])\n",
    "        visited = set()\n",
    "        visited.add(start)\n",
    "        while(que):\n",
    "            u, step = que.popleft()\n",
    "            for v in graph[u]:\n",
    "                if(v not in visited):\n",
    "                    visited.add(v)\n",
    "                    que.append([v,step+1])\n",
    "        return step\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        graph = {}\n",
    "        def traversal(root,fa):\n",
    "            if(not root):\n",
    "                return\n",
    "            if(root.val not in graph):\n",
    "                graph[root.val] = []\n",
    "            if(fa):\n",
    "                graph[root.val].append(fa.val)\n",
    "            if(root.left):\n",
    "                graph[root.val].append(root.left.val)\n",
    "            if(root.right):\n",
    "                graph[root.val].append(root.right.val)\n",
    "            traversal(root.left,root)\n",
    "            traversal(root.right,root)\n",
    "            return\n",
    "        traversal(root,None)\n",
    "        que = deque()\n",
    "        que.append([start,0])\n",
    "        visited = set()\n",
    "        visited.add(start)\n",
    "        while(que):\n",
    "            u, step = que.popleft()\n",
    "            for v in graph[u]:\n",
    "                if(v not in visited):\n",
    "                    visited.add(v)\n",
    "                    que.append([v,step+1])\n",
    "        return step\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "                g = defaultdict(list)\n",
    "                \n",
    "                def dfs(root):\n",
    "                    if not root:return\n",
    "                    if root.left:\n",
    "                        g[root.val].append(root.left.val)\n",
    "                        g[root.left.val].append(root.val)\n",
    "                        dfs(root.left)\n",
    "                    if root.right:\n",
    "                        g[root.val].append(root.right.val)\n",
    "                        g[root.right.val].append(root.val)\n",
    "                        dfs(root.right)\n",
    "                dfs(root)\n",
    "                \n",
    "                q = deque([start])\n",
    "                d = -1;vis = set();vis.add(start)\n",
    "                while q:\n",
    "                    size = len(q)\n",
    "                    for _ in range(size):\n",
    "                        w = q.popleft()\n",
    "                        for u in g[w]:\n",
    "                            if u not in vis:\n",
    "                                q.append(u)\n",
    "                                vis.add(u)\n",
    "                    d += 1\n",
    "                return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "    \t\t\t\tg = defaultdict(list)\n",
    "    \t\t\t\tdef dfs(root: Optional[TreeNode], p: int) -> None:\n",
    "    \t\t\t\t\t\t\t\tif p != -1:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tg[root.val].append(p)\n",
    "    \t\t\t\t\t\t\t\tif root.left:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tg[root.val].append(root.left.val)\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tdfs(root.left, root.val)\n",
    "    \t\t\t\t\t\t\t\tif root.right:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tg[root.val].append(root.right.val)\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tdfs(root.right, root.val)\n",
    "    \t\t\t\tdfs(root, -1)\n",
    "    \t\t\t\tstep = -1\n",
    "    \t\t\t\tq = deque()\n",
    "    \t\t\t\tq.append(start)\n",
    "    \t\t\t\tvis = set()\n",
    "    \t\t\t\tvis.add(start)\n",
    "    \t\t\t\twhile q:\n",
    "    \t\t\t\t\t\t\t\tsize = len(q)\n",
    "    \t\t\t\t\t\t\t\tfor _ in range(size):\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tp = q.popleft()\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tfor y in g[p]:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tif y not in vis:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tvis.add(y)\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tq.append(y)\n",
    "    \t\t\t\t\t\t\t\tstep += 1\n",
    "    \t\t\t\treturn step\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\t\n",
    "    \t\t\t\t\t\t\t\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        graph = {}\n",
    "        def traversal(root,fa):\n",
    "            if(not root):\n",
    "                return\n",
    "            if(root.val not in graph):\n",
    "                graph[root.val] = []\n",
    "            if(fa):\n",
    "                graph[root.val].append(fa.val)\n",
    "            if(root.left):\n",
    "                graph[root.val].append(root.left.val)\n",
    "            if(root.right):\n",
    "                graph[root.val].append(root.right.val)\n",
    "            traversal(root.left,root)\n",
    "            traversal(root.right,root)\n",
    "            return\n",
    "        traversal(root,None)\n",
    "        que = deque()\n",
    "        que.append([start,0])\n",
    "        visited = set()\n",
    "        visited.add(start)\n",
    "        while(que):\n",
    "            u, step = que.popleft()\n",
    "            for v in graph[u]:\n",
    "                if(v not in visited):\n",
    "                    visited.add(v)\n",
    "                    que.append([v,step+1])\n",
    "        return step\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        def dfs(node, pre):\n",
    "            if not node:\n",
    "                return\n",
    "            v = node.val\n",
    "            if pre != -1:\n",
    "                g[v].append(pre)\n",
    "            if node.left:\n",
    "                g[v].append(node.left.val)\n",
    "                dfs(node.left, v)\n",
    "            if node.right:\n",
    "                g[v].append(node.right.val)\n",
    "                dfs(node.right, v)\n",
    "        \n",
    "        dfs(root, -1)\n",
    "        \n",
    "        q = deque([(0, start)])\n",
    "        s = set([start])\n",
    "        while q:\n",
    "            d, node = q.popleft()\n",
    "            for ch in g[node]:\n",
    "                if ch not in s:\n",
    "                    s.add(ch)\n",
    "                    q.append((d + 1, ch))\n",
    "\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "\n",
    "        graph={}\n",
    "\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            v=root.val\n",
    "            if v not in graph:\n",
    "                graph[v]=[]\n",
    "\n",
    "            if root.left:\n",
    "                l=root.left.val\n",
    "                if l not in graph:\n",
    "                    graph[l]=[]\n",
    "                graph[v].append(l)\n",
    "                graph[l].append(v)\n",
    "                inorder(root.left)\n",
    "            if root.right:\n",
    "                r=root.right.val\n",
    "                if r not in graph:\n",
    "                    graph[r]=[]\n",
    "                graph[v].append(r)\n",
    "                graph[r].append(v)\n",
    "                inorder(root.right)\n",
    "        inorder(root)\n",
    "        print(graph)\n",
    "\n",
    "        result=-1\n",
    "        queue=deque([start])\n",
    "        seen=set([start])\n",
    "\n",
    "        while queue:\n",
    "            result+=1\n",
    "            for _ in range(len(queue)):\n",
    "                curr=queue.popleft()\n",
    "                for child in graph[curr]:\n",
    "                    if child not in seen:\n",
    "                        queue.append(child)\n",
    "                        seen.add(child)\n",
    "            \n",
    "        \n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        # I want to change it into a graph\n",
    "        hashmap_list = collections.defaultdict(list)\n",
    "        def dfs(root):\n",
    "            val = root.val\n",
    "            if root.left != None:\n",
    "                left_val = root.left.val\n",
    "                hashmap_list[val].append(left_val)\n",
    "                hashmap_list[left_val].append(val)\n",
    "                dfs(root.left)\n",
    "            if root.right != None:\n",
    "                right_val = root.right.val\n",
    "                hashmap_list[val].append(right_val)\n",
    "                hashmap_list[right_val].append(val)\n",
    "                dfs(root.right)\n",
    "            return\n",
    "        dfs(root)\n",
    "        hashmap_isvisited = collections.defaultdict(int)\n",
    "        queue = collections.deque()\n",
    "        hashmap_isvisited[start] = 1\n",
    "        queue.append((start, 0))\n",
    "        res = 0\n",
    "        while queue:\n",
    "            node, depth = queue.popleft()\n",
    "            res = max(depth, res)\n",
    "            for neighbor in hashmap_list[node]:\n",
    "                if hashmap_isvisited[neighbor] == 0:\n",
    "                    hashmap_isvisited[neighbor] = 1\n",
    "                    queue.append((neighbor, depth + 1))\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        \n",
    "        dct = defaultdict(list)\n",
    "        nodes = set()\n",
    "        \n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \n",
    "            nodes.add(node.val)\n",
    "            if node.left:\n",
    "                dct[node.left.val].append(node.val)\n",
    "                dct[node.val].append(node.left.val)\n",
    "                dfs(node.left)\n",
    "            if node.right:\n",
    "                dct[node.right.val].append(node.val)\n",
    "                dct[node.val].append(node.right.val)\n",
    "                dfs(node.right)\n",
    "            return \n",
    "        \n",
    "        dfs(root)\n",
    "        \n",
    "        \n",
    "        ans = 0\n",
    "        stack = deque([[start, -1, 0]])\n",
    "        while stack:\n",
    "            x, fa, d = stack.popleft()\n",
    "            ans = ans if ans > d else d\n",
    "            for y in dct[x]:\n",
    "                if y != fa:\n",
    "                    stack.append([y, x, d+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import queue\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        map = {}\n",
    "        def dfs(root):\n",
    "            rootv = root.val\n",
    "            left, right = root.left, root.right\n",
    "            if left is None and right is None:\n",
    "                return\n",
    "            if rootv not in map:\n",
    "                map[rootv] = []\n",
    "            if left is not None:\n",
    "                lv = left.val\n",
    "                if lv not in map:\n",
    "                    map[lv] = []\n",
    "                map[lv].append(rootv)\n",
    "                map[rootv].append(lv)\n",
    "                dfs(root.left)\n",
    "            if right is not None:\n",
    "                rv = right.val\n",
    "                if rv not in map:\n",
    "                    map[rv] = []\n",
    "                map[rv].append(rootv)\n",
    "                map[rootv].append(rv)\n",
    "                dfs(root.right)\n",
    "\n",
    "        dfs(root)\n",
    "        # print(f'遍历后的图:{map}')\n",
    "\n",
    "        q = queue.Queue()\n",
    "        q.put(start)\n",
    "        visited = set()\n",
    "\n",
    "        step = -1\n",
    "        while q.qsize() > 0:\n",
    "            size = q.qsize()\n",
    "            for _ in range(size):\n",
    "                prev = q.get()\n",
    "                if prev not in map:\n",
    "                    continue\n",
    "                for next in map[prev]:\n",
    "                    if next not in visited:\n",
    "                        q.put(next)\n",
    "                visited.add(prev)\n",
    "            step += 1\n",
    "\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import queue\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        map = {}\n",
    "        def dfs(root):\n",
    "            rootv = root.val\n",
    "            left, right = root.left, root.right\n",
    "            if left is None and right is None:\n",
    "                return\n",
    "            if rootv not in map:\n",
    "                map[rootv] = []\n",
    "            if left is not None:\n",
    "                lv = left.val\n",
    "                if lv not in map:\n",
    "                    map[lv] = []\n",
    "                map[lv].append(rootv)\n",
    "                map[rootv].append(lv)\n",
    "                dfs(root.left)\n",
    "            if right is not None:\n",
    "                rv = right.val\n",
    "                if rv not in map:\n",
    "                    map[rv] = []\n",
    "                map[rv].append(rootv)\n",
    "                map[rootv].append(rv)\n",
    "                dfs(root.right)\n",
    "\n",
    "        dfs(root)\n",
    "        # print(f'遍历后的图:{map}')\n",
    "\n",
    "        q = queue.Queue()\n",
    "        q.put(start)\n",
    "        visited = set()\n",
    "\n",
    "        step = -1\n",
    "        while q.qsize() > 0:\n",
    "            size = q.qsize()\n",
    "            for _ in range(size):\n",
    "                prev = q.get()\n",
    "                if prev not in map:\n",
    "                    continue\n",
    "                for next in map[prev]:\n",
    "                    if next not in visited:\n",
    "                        q.put(next)\n",
    "                visited.add(prev)\n",
    "            step += 1\n",
    "\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        graph = {}\n",
    "        def add_edge(u, v):\n",
    "        # 添加无向图的边\n",
    "            nonlocal graph\n",
    "            if u in graph:\n",
    "                graph[u].append(v)\n",
    "            else:\n",
    "                graph[u] = [v]\n",
    "        def dfs(node):\n",
    "            if node == None:\n",
    "                return\n",
    "            \n",
    "            if node.left:\n",
    "                add_edge(node.val, node.left.val)\n",
    "                add_edge(node.left.val, node.val)\n",
    "                dfs(node.left)\n",
    "            \n",
    "            if node.right:\n",
    "                add_edge(node.val, node.right.val)\n",
    "                add_edge(node.right.val, node.val)\n",
    "\n",
    "                dfs(node.right)\n",
    "            \n",
    "        dfs(root)\n",
    "        #print(graph)\n",
    "        if len(graph) == 0:\n",
    "            return 0\n",
    "\n",
    "        # bfs\n",
    "        queue = [start]\n",
    "        seen = set([start])\n",
    "        res = 0\n",
    "        while queue:\n",
    "            newqueue = []\n",
    "            #print(queue)\n",
    "            for node in queue:\n",
    "                for neighbor in graph[node]:\n",
    "                    if neighbor not in seen:\n",
    "                        newqueue.append(neighbor)\n",
    "                        seen.add(neighbor)\n",
    "            queue = newqueue\n",
    "            res += 1\n",
    "        \n",
    "        return res - 1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:\n",
    "        parent = {root.val: None}\n",
    "\n",
    "        def findParent(root):\n",
    "            if not root: return\n",
    "\n",
    "            if root.left:\n",
    "                parent[root.left.val] = root\n",
    "                findParent(root.left)\n",
    "            \n",
    "            if root.right:\n",
    "                parent[root.right.val] = root\n",
    "                findParent(root.right)\n",
    "        \n",
    "        findParent(root)\n",
    "        answer = 0\n",
    "\n",
    "        def findTarget(node):\n",
    "            if not node: return None\n",
    "            return node if node.val == start else (findTarget(node.left) or findTarget(node.right))\n",
    "        \n",
    "        target = findTarget(root)\n",
    "\n",
    "        def helper(root, prev, minutes):\n",
    "            if not root:\n",
    "                return\n",
    "            nonlocal answer\n",
    "            answer = max(answer, minutes)\n",
    "\n",
    "            for node in root.left, root.right, parent[root.val]:\n",
    "                if node != prev:\n",
    "                    helper(node, root, minutes + 1)\n",
    "\n",
    "            \n",
    "        helper(target, None, 0)\n",
    "        return answer"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
